class Solution(object):
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        length = len(s1)
        DP = [[[[False for _ in range(length)] for _ in range(length)] for _ in range(length)] for _ in range(length)]
        for k in range(length):
            for i in range(length - k):
                for m in range(length - k):
                    if k == 0:
                        DP[i][i][m][m] = s1[i] == s2[m]
                    else:
                        flag = False
                        for t in range(k):
                            flag = flag or (DP[i][i + t][m][m + t] and DP[i + t + 1][i + k][m + t + 1][m + k]) or (
                                        DP[i][i + t][m + k - t][m + k] and DP[i + t + 1][i + k][m][m + k - t - 1])
                            if flag:
                                break
                        DP[i][i + k][m][m + k] = flag
        return DP[0][-1][0][-1]


data = Solution()
s1 = "a"
s2 = "a"
print(data.isScramble(s1, s2))
s1 = "abb"
s2 = "bba"
print(data.isScramble(s1, s2))
s1 = "ab"
s2 = "ba"
print(data.isScramble(s1, s2))
s1 = "onpaghkfbpchutcxqxxynyecrhmcce"
s2 = "ocyhcnxqcexptnfbxrcegpuhckhyam"
print(data.isScramble(s1, s2))